from time import clock

#class topo is used to route
class topo:
    def __init__(self):
        self.quantity = 0
        self.matrix = {}
        self.distance = []
    def load(self, topology):
        topoloader = open(topology, 'r')
        topolines = topoloader.readlines()
        for topoline in topolines:
            tricell = topoline.split()
            if len(tricell) == 1:
                self.quantity = int(tricell[0])
                for i in range(self.quantity):
                    self.distance.append([])
                    for j in range(self.quantity):
                        self.distance[i].append(-1)
            if len(tricell) == 3:
                self.matrix[(int(tricell[0]), int(tricell[1]))] = float(tricell[2])
                self.matrix[(int(tricell[1]), int(tricell[0]))] = float(tricell[2])
        print 'Topology loaded'
        topoloader.close()
    def floyd_warshall(self):
        for key, distance in self.matrix.items():
            self.distance[key[0]][key[1]] = distance
            self.distance[key[1]][key[0]] = distance
        k = 0
        print 'here', self.quantity
        for k in range(self.quantity):
            i = 0
            for i in range(self.quantity):
                j = 0
                if self.distance[i][k] != -1:
                    #print 'i, k:' + str(i) + ',' + str(k)
                    ref = self.distance[i][k]
                else:
                    continue
                for j in range(self.quantity):
                    if i == j:
                        continue
                    if self.distance[k][j] != -1:
                        subref = self.distance[k][j]
                        #print 'k, j:' + str(k) + ',' + str(j)
                        if self.distance[i][j] != -1:
                            #print 'dist i,j:' + str(i) + ',' + str(j)
                            if ref + subref < self.distance[i][j]:
                                self.distance[i][j] = ref + subref
                        else:
                            #print 'no dist i,j:' + str(i) + ',' + str(j)
                            self.distance[i][j] = ref + subref
    def output(self):
        print '----------Distance----------'
        for i in range(self.quantity):
            for j in range(self.quantity):
                print i,j,
                print '=' + str(self.distance[i][j])
        print

#tpo = topo()
#tpo.load('../topo.in')
#c1 = clock()
#tpo.floyd_warshall()
#print 'time:', clock() - c1
#tpo.output()

